package 排序;

public class QuickSort<E extends Comparable<E>> extends Sort<E>{

	@Override
	protected void sort() {
		sort(0, array.length);
	}
	
	/**
	 * 对[begin, end)内的元素进行快速排序
	 * @param begin
	 * @param end
	 */
	private void sort(int begin, int end) {
		if (end - begin < 2) return;
		// 确定轴点
		int mid = pivotIndex(begin, end);
		// 对左右两边进行快速排序
		sort(begin, mid);
		sort(mid + 1, end);
	}
	
	/**
	 * 将轴点元素(首元素)放在合适位置后返回轴点索引
	 * @param begin
	 * @param end
	 * @return
	 */
	private int pivotIndex(int begin, int end) {
		swap(begin, begin + (int)(Math.random() * (end - begin)));
		// 备份轴点元素
		E pivot = array[begin];
		end--;
		while (begin < end) {
			while (begin < end) {
				if (cmp(pivot, array[end]) < 0) {
					end--;
				} else {
					array[begin++] = array[end];
					break;
				}
			}
			
			while (begin < end) {
				if (cmp(pivot, array[begin]) > 0) {
					begin++;
				} else {
					array[end--] = array[begin];
					break;
				}
			}
			
		}
		array[begin] = pivot;
		return begin;
	}

}
